from typing import List


class Solution:
    def minCapability(self, nums: List[int], k: int) -> int:
        inf = float('inf')
        n = len(nums)
        dp = [[[0 for _ in range(2)] for _ in range(k + 1)] for _ in range(n)]
        min_get = inf
        dp[0][0][0] = 0
        dp[0][1][1] = nums[0]
        for i in range(1, n):
            for j in range(k + 1):
                dp[i][j][0] = max(dp[i - 1][j])
                if j > 0:
                    dp[i][j][1] = max(dp[i - 1][j - 1][0], nums[i])
                if i >= 2 * k - 2:
                    min_get = min(min_get, dp[i][k][j])
        return min_get


if __name__ == '__main__':
    s = Solution()
    r = s.minCapability(nums=[2, 3, 5, 9], k=2)
    print(r)
